#include <iostream>
#include <algorithm>

/**
 *@file DoubleLinkedList.h
 *@author zq
 *@data 2022/10/7
 */

/**
 *@brief List模板类
 */
template <typename DT>
class List
{
 private:
  struct Node   ///链表节点，用于储存数据并提供前后相连节点的地址
  {
    DT data;
    Node *prev;
    Node *next;
    
    Node( const DT & d = DT{ }, Node * p = nullptr, Node * n = nullptr )
    : data{ d }, prev{ p }, next{ n } { }
    
    Node( DT && d, Node * p = nullptr, Node * n = nullptr )
    : data{ std::move( d ) }, prev{ p }, next{ n } { }
  };
  
 public:
  /**
   *@brief const迭代器
   */
  class const_iterator
  {
    public:
      const_iterator( ) : current{ nullptr }
        { }
    
      const DT & operator* ( ) const
        { return retrieve( ); }
    
      const_iterator & operator++ ( )
        {
	  current = current->next;
	  return *this;
        }
    
      const_iterator operator++ ( int )
        {
          const_iterator old = *this;
          ++( *this );
          return old;
        }
    
      bool operator== ( const const_iterator & rhs ) const
        { return current == rhs.current; }
      bool operator!= ( const const_iterator & rhs ) const
        { return !( *this == rhs ); }
    
    protected:
      Node *current;
    
      DT & retrieve( ) const
        { return current->data; }
    
      const_iterator( Node *p ) : current{ p }
        { }
    
      friend class List<DT>; };

  /**
   *@brief 可变迭代器
   */
  class iterator : public const_iterator
  {
    public:
      iterator( )
        { }
      DT & operator* ( )
        { return const_iterator::retrieve( ); }
      const DT & operator* ( ) const
        { return const_iterator::operator*( ); }
      iterator & operator++ ( )
      {
	this->current = this->current->next;
	return *this;
      }
      iterator operator++ ( int )
      {
        iterator old = *this;
        ++( *this );
        return old;
      }
    protected:
      iterator( Node *p ) : const_iterator{ p }
        { }
      friend class List<DT>;
  };
  
 public:
  List( )
    { init( ); }
  ~List( )
    {
      clear( );
      delete head;
      delete tail;
    }
  List( const List & rhs )
    {
      init( );
      for( auto & x : rhs )
	push_back( x );
    }
  List & operator= ( const List & rhs )
    {
      List copy = rhs;
      std::swap( *this, copy );
      return *this;
    }
  List( List && rhs ): theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
    {
      rhs.theSize = 0;
      rhs.head = nullptr;
      rhs.tail = nullptr;
    }
  List & operator= ( List && rhs )
    {
      std::swap( theSize, rhs.theSize );
      std::swap( head, rhs.head );
      std::swap( tail, rhs.tail );
      
      return *this;
    }
  /**
   *@brief 用于找到链表的地一个节点
   *
   *@return 返回链表的第一个节点
   */
  iterator begin( )
  { return { head->next }; }
  const_iterator begin( ) const
  { return { head->next }; }
  iterator end( )
  { return { tail }; }
  const_iterator end( ) const
  { return { tail }; }
  
  int size( ) const
  { return theSize; }
  bool empty( ) const
  { return size( ) == 0; }
  
  /**
   *@brief 用于清空链表
   *
   */
  void clear( )
  {
    while( !empty( ) )
      pop_front( );
  }
  DT & front( )
    { return *begin( ); }
  const DT & front( ) const
    { return *begin( ); }
  DT & back( )
    { return *--end( ); }
  const DT & back( ) const
    { return *--end( ); }
  /**
   *@brief 用于插入x在链表的开头
   *
   *@param x 插入的节点中的数据
   */
  void push_front( const DT & x )
    { insert( begin( ), x ); }
  void push_front( DT && x )
    { insert( begin( ), std::move( x ) ); }
  /**
   *@brief 用于插入x在链表的结尾
   *
   *@param x 插入的节点中的数据
   */
  void push_back( const DT & x )
    { insert( end( ), x ); }
  void push_back( DT && x )
    { insert( end( ), std::move( x ) ); }
  /**
   *@brief 用于删除链表的第一个节点
   *
   */
  void pop_front( )
    { erase( begin( ) ); }
  /**
   *@brief 用于删除链表的最后一个节点
   *
   */
  void pop_back( )
    { erase( --end( ) ); }
  
  // Insert x before itr.
  /**
   *@brief 用于在特定位置加入特定节点，并保持链表的连续
   *
   *@param itr 在该节点前插入新节点
   *@param x 插入的新节点中的数据
   */
  iterator insert( iterator itr, const DT & x )
  {
    Node *p = itr.current;
    theSize++;
    return { p->prev = p->prev->next = new Node{ x, p->prev, p } };
  }
  // Insert x before itr.
  iterator insert( iterator itr, DT && x )
  {
    Node *p = itr.current;
    theSize++;
    return { p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } };
  }
  /**
   *@brief 用于删除特定链表节点，并保持链表的连续
   *
   *@param itr 输入待删节点
   *@return 返回该节点的下一个节点
   *@retval 返回值为iterator
   */
  iterator erase( iterator itr )
  {
    Node *p = itr.current;
    iterator retVal{ p->next };
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    theSize--;
    return retVal;
  }
  /**
   *@brief 用于删除特定连续的链表节点，并保持链表的连续
   *
   *@param from 待删除节点的头节点
   *@param to 待删除节点的尾节点
   *@return 返回尾节点
   *@retval 返回值为iterator
   */
  iterator erase( iterator from, iterator to )
  {
    for( iterator itr = from; itr != to; )
      itr = erase( itr );
    return to;
  }

 private:
  int theSize;
  Node *head;
  Node *tail;
  
  void init( )  ///List的构造函数
  {
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
  }
};
